The present invention relates to computer networks and in particular to a routing system increasing effective network bandwidth.
Computer networks provide for the exchange of digital data among computers over a variety of media including electrical cable, optical fiber, and radio links. Commonly, the data is broken into data packets each provided with a header indicating a destination for the packet and a packet sequence number. The packets are forwarded over a complex and changing network topology through the agency of “routers” which read the packet headers and forward the packets on particular links to other routers according to a router table. At the destination, the packets are reassembled.
The term “router” as used herein will refer broadly to any network node processing data packets for the purpose of communicating them through a network and may include hubs, switches, and bridges as well as conventional routers.
The bandwidth of a network is a general measure of the rate of data transfer that can be obtained. Limits on bandwidth can include physical limitations in the media of the links between nodes, for example, caused by the impendence of electrical conductors, as well as processing limitations of the node hardware. While bandwidth limitations can generally be addressed by over-provisioning the network (e.g. adding additional links and faster hardware) these measures can be costly. Increased demand for high bandwidth content (e.g. video) and the importance of accommodating highly variable network traffic, for example “flash crowds”, makes it desirable to find ways to increase the bandwidth efficiency of existing networks.
The effective bandwidth of the network may be effectively increased by a number of software techniques. “Traffic engineering” may be used to allocate the routing of data to spread the load evenly across network links. This technique, by eliminating congestion, improves the effective bandwidth of the network. Traffic engineering can be limited, however, by the difficulty of anticipating rapid variation in traffic volumes and coordinating spatially separate routers.
Data compression can also be used to increase the effective bandwidth of the network. Thus, for example, video can be compressed using an MPEG compression system to significantly decrease the amount of data required to support a video transmission. Some compression can be accomplished in this manner by the network operator trapping and converting files.
Application layer caching can also be used to improve the effective bandwidth of a network by taking commonly used network data and placing it in proxy caches at various locations on the network. The proxy caches limit the need to transmit the data over the network when it is subject to separated requests.
Improved network capacity can also be provided by monitoring and removing packet-level redundancy, for example, at network routers. Such systems will be termed “redundancy-aware routers” and generally operate independently of the application layer by inspecting packets for redundancy, removing the redundant strings from the packets, and allowing the removed material to be replaced at the destination from a downstream cache.